#ifndef STACK_H
#define STACK_H

typedef int DataType;

struct BinTreeNode {
        DataType val;
        struct BinTreeNode *left;
        struct BinTreeNode *right;
};
typedef struct BinTreeNode *PBinTreeNode;
typedef struct BinTreeNode *BinTree;

typedef BinTree DataType_s_q;

#define MAX_NUM 100
#define FLAG 0

enum bool {
        false, true
};
typedef enum bool Bool;


struct Node {
        DataType_s_q val;
        struct Node *next;
};
typedef struct Node *PNode;
typedef struct Node *LinkList;

struct LinkStack {
        LinkList top;
        int len;
        int MAXNUM;
};
typedef struct LinkStack *PLinkStack;

// six functions.
PLinkStack createEmptyStack_link(void);
Bool isEmptyStack_link(PLinkStack plstack);
Bool Stack_is_full(PLinkStack plstack);
void push_link(PLinkStack plstack, DataType_s_q x);
void pop_link(PLinkStack plstack);
DataType_s_q top_link(PLinkStack plstack);

// 注意：我们的链栈没有头结点.
PLinkStack createEmptyStack_link(void)
{
        PLinkStack plstack = (PLinkStack)malloc(sizeof(struct LinkStack));
        plstack->top = NULL;
        plstack->len = 0;
        plstack->MAXNUM = MAX_NUM;
        return plstack;
}

Bool isEmptyStack_link(PLinkStack plstack)
{
        return plstack->top     == NULL;
}

Bool Stack_is_full(PLinkStack plstack)
{
        return plstack->len >= plstack->MAXNUM;
}

// 在栈顶头结点下面开始插入元素.
void push_link(PLinkStack plstack, DataType_s_q x)
{
        // 入栈，首先判断栈是否满.
        if (Stack_is_full(plstack)) {
                printf("The Stack is full! Can't push element now!\n");
                return ;
        }
        // 不满就开辟新结点，插入之.
        PNode p = (PNode)malloc(sizeof(struct Node));
        p->val = x;
        // 先立新，再破旧.
        p->next = plstack->top;
        plstack->top = p;
}

DataType_s_q top_link(PLinkStack plstack)
{
        if (!plstack->top) return NULL;
        return plstack->top->val;
}

// 虽然进行了pop操作，但top指针依然指向链表的第一个元素，因为我们采用的是头插法和头删法.
void pop_link(PLinkStack plstack)
{
        if (isEmptyStack_link(plstack)) {
                printf("Now the stack is empty! Can't pop!\n");
                return ;
        }
        plstack->top = plstack->top->next;
}

void print_Stack(PLinkStack S)
{
        if (isEmptyStack_link(S)) {
                printf("Now the stack is empty!\n");
                return ;
        }
        PNode p;
        for (p = S->top; p != NULL; p = p->next) {
                printf("%p ", p->val);
        }
        printf("\n");
}
#endif
